Data processing applications often include functions for determining minimum or maximum values (referred herein as, “extremum,” or “extreme value”) in a given data set. For example, multimedia applications such as image processing, video compression, noise reduction, or motion estimation may require determination of extreme values in a two dimensional array of pixel data. Digital signal processors may search for extreme values in a sampled set of frequencies in a frequency spectrum. Other applications are known in the art which utilize the calculation of extreme values in a multi-dimensional array. Moreover, the applications may also utilize information regarding the location of the extreme value within the multi-dimensional array.
Specialized instructions are typically employed in data processing systems for searching extreme values in data sets stored as vectors or two dimensional arrays. The data set which is subjected to the search may reside in a memory system associated with the data processor. In the case of data sets stored as two dimensional arrays, a first approach may utilize instructions to read the data elements from the two dimensional array, one row at a time, and perform a search for an extreme value within each row. The extreme value can be found by walking through the row, comparing each data element with a running value indicating a current extreme value, and updating the running value if necessary, and wherein the running value at the end of all such comparisons within a row is the extreme value of the row. Alternately, the extreme value may be determined by a pair-wise tree type reduction of extreme values of data elements in the row (this technique is explained further below with reference to computation of extreme value of vector 106 of FIG. 1). Once the extreme value of each row is calculated by any suitable technique, a global extremum from the calculated extreme values for each row may be determined, in order to establish the extremum of the two dimensional array. Instructions may then search through the two dimensional array for the occurrence of the extremum so determined, in order to find the address of the extremum within the two dimensional array.
There are drawbacks to the above first approach of searching for extreme values. Firstly, the data processing system must provide additional temporary storage space for storing the intermediate calculations of extreme values within each row. Secondly, the above method comprising the steps of calculating the extreme value within a row; calculating the global extremum; and then searching for a location of the global extremum within the two dimensional array incurs considerable wastage of system resources in terms of the number of instructions used for the entire operation, temporary storage space and latency of the entire operation. Thirdly, a major drawback of the first approach is the necessity of having to search through the two dimensional array for the occurrence of the global extremum, once the global extremum has been determined. This search may require reading each row of the two dimensional array and comparing the data elements of the row with the global extremum to determine which row of the two dimensional array contains the determined global extremum. Moreover, intervening read/write operations to any of the rows within the two dimensional array must be held in abeyance until the entire operation is completed.
Some processing systems may adopt a second approach to overcome the drawbacks of the first approach. FIG. 1 is a schematic illustration of the second approach. A description of the second approach is provided below for the case where an extreme value is a maximum value. The approach is similar for the case where an extreme value is a minimum value.
With reference to FIG. 1, there is shown a two dimensional array 100 of two rows, 102 and 104. Each row, 102 and 104, is a vector comprising four data elements, 102a-102d and 104a-104d respectively. In a first stage (Stage 1) of determining a maximum value of the array 100, a lane-wise maximum is calculated for each pair of data elements in the same column as shown. A vector instruction, such as, a single instruction multiple data (SIMD) type instruction may be used for performing such vector operations. Each element of vector 106, i.e. 106a-106d now contains the maximum value in each column of array 100. For example, 106a is the maximum value of data elements 102a and 104a, and so on.
Stage 2 marks the onset of calculating a global maximum. Stage 2 begins by first computing intermediate maximum values 108a/b and 108c/d, such that 108a/b is the maximum value of 106a and 106b, and 108c/d is the maximum value of 106c and 106d. Next, the maximum value of 108a/b and 108c/d is computed and determined to be the global maximum 110 of array 100. This type of pair-wise reduction of the vector to a single value, such as the global maximum 110, is known in the art as a tree type reduction. Skilled persons will also recognize that for arrays with larger number of rows, the vector 106 comprising lane-wise maximum values may be determined by dividing the array into pairs of rows similar to 102 and 104, computing intermediate lane-wise maximum vectors for each pair of rows, and repeating the process with the intermediate lane-wise maximum vectors until a global maximum is calculated. Accordingly, by dividing the array and performing computations in parallel using SIMD type instructions, the global extremum may be calculated in a faster and more efficient manner than the first approach.
However, stage 3 of the second approach shares a major drawback of the first approach. Stage 3 comprises the step of searching for the occurrence of the global maximum 110 in array 100. Like in the first approach, this step is computationally intensive and wasteful on system resources.
Accordingly, there is a need in the art for techniques which overcome the drawbacks of the first and second approaches, and provide for fast and efficient searching of extreme values in a multi-dimensional array, along with determining the location of occurrence of the extreme value within the array.